package com.wjy.Data_Structure.sort;

import com.wjy.Data_Structure.strategy.Strategy;

public class Sort {
	private Strategy strategy = new IntStrategy();

	/**
	 * 直接插入排序
	 * 
	 * @param r数据元素数组
	 * @param low
	 * @param hight
	 *            数组r 的待排序区间[low..high]
	 */
	public void insertSort(Object[] r, int low, int hight) {
		for (int i = low + 1; i <= hight; i++)
			if (strategy.compare(r[i], r[i - 1]) < 0) { // 小于时，需将r[i]插入有序表
				Object temp = r[i];
				r[i] = r[i - 1];
				int j = i - 2;
				for (; j >= low && strategy.compare(temp, r[j]) < 0; j--)
					r[j + 1] = r[j]; // 记录后移
				r[j + 1] = temp;// 插入到正确位置
			}
	}

	/**
	 * 折半插入排序
	 * 
	 * @param r数据元素数组
	 * @param low
	 * @param hight
	 *            数组r 的待排序区间[low..high]
	 */
	public void binInsertSort(Object[] r, int low, int high) {
		for (int i = low + 1; i <= high; i++) {
			Object temp = r[i]; // 保持待插入元素
			int hi = i - 1;
			int lo = low; // 设定初始区间
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (strategy.compare(temp, r[mid]) < 0)
					hi = mid - 1;
				else
					lo = mid + 1;
			}
			for (int j = i - 1; j > hi; j--) {
				r[j + 1] = r[j];
				r[hi + 1] = temp;
			}
		}

	}
}
